1. Field of the Invention
The invention relates in general to the design of electronic circuits and more particularly to logic synthesis.
2. Description of the Related Art
In general, logic synthesis involves conversion of a more abstract higher level description of intended behavior of a circuit design to a less abstract more specific lower level description of circuit elements and their interconnection that can implement the intended behavior. For example, a synthesis process may convert a register transfer level (RTL) description of desired circuit behavior to a gate level description of a circuit that implements that behavior. Logic synthesis processes often employ optimization techniques. For example, optimization criteria, such as minimizing gate count or minimizing the number of levels in a combinational logic circuit, may guide the development of a circuit implementation that exhibits desired behavior. More particularly, a synthesis process may employ a cost function in accordance with an optimization technique to determine what combination of logic gates and their interconnection to employ in a circuit implementation. A synthesis process typically produces a circuit implementation that includes combinational logic elements.
Often, one goal of a logic synthesis process is to implement intended behavior specified as a Boolean function f as a combinational circuit, which is optimized with respect to some cost function. An optimization algorithm (or process) may be used to achieve optimization relative to a cost function. Certain optimization algorithms may be tuned to direct a synthesis process according to one or more criteria specified through a cost function. Scalable logic optimization algorithms are desirable since the number circuit elements in combinational logic blocks (i.e. blocks of combinational circuit elements) may be large in modem integrated circuits (ICs). Preferably, a scalable algorithm for an optimization problem exhibits polynomial (in practice, close to linear) complexity, and operates to select an optimal solution from a “large” portion of the search space.
Multi-level logic synthesis can be performed using algebraic means such as factorization as described in R. Brayton and C. McMullen, “The Decomposition and Factorization of Boolean Expressions,” in Proc. IEEE International Symposium on Circuits and Systems, pp. 49-54, May 1982, or using kerneling as described by R. Brayton and C. McMullen. and as described in J. Vasudevamurthy and J. Rajski, “A Method for Concurrent Decomposition and Factorization of Boolean Expressions,” in Proc. of IEEE International Conference on Computer-Aided Design, pp. 510-513, November 1990. Although these techniques are fast, being algebraic, they explore only a limited portion of the optimization space. Other ODC techniques described in H. Savcj and R. Brayton, “The Use of Observability and External Don't Cares for the Simplification of Multi-Level Networks,” in Proc. of ACM/IEEE Design Automation Conference, pp. 297-301, June 1990 and in H. Savoj, R. Brayton, and H. Touati, “Extracting Local Don't Cares for Network Optimization,” in Proc. of IEEE International Conference on Computer-Aided Design, pp. 514-517, November 1991 and other CODC techniques described in H. Savoj, Don't Cares in Multi-Level Network Optimization. PhD thesis, University of California Berkeley, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, Calif. 94720, May 1992, perform “don't care” based optimization, but they do not modify the structure of the circuit. Although occasionally a node gets removed as a result of “don't care” based optimization, such an occurrence is rare. Toggle equivalence is different from the algebraic techniques, since it explores the “Boolean” options in the search space, while it differs from multi-level “don't care” based techniques since it does not restrict itself to the original network topology.
In E. Goldberg, On Equivalence Checking and Logic Synthesis of Circuits with a Common Specification, GLSVLSI, Chicago, Apr. 17-19, 2005, pp. 102-107 and commonly assigned U.S. Pat. No. 7,380,226, entitled, Method and Apparatus to Perform Logic Synthesis Preserving High-Level Specification, issued May 27, 2008, invented by E. Goldberg, (the “TEQLS references”) a new method of logic synthesis was introduced. This method is referred to as TEQLS (pronounced “tickles”), which stands for Toggle Equivalence-preserving Logic Synthesis. Each of the TEQLS references is expressly incorporated herein by this reference as if expressly set forth herein in its entirety.
As shown in FIG. 1, assume that a partitioning of N into subcircuits Ni, i=1, 2, . . . , k is specified. A goal of the TEQLS method is to optimize N by replacing each subcircuit Ni with a toggle equivalent counterpart Ni*, i=1, 2, . . . , k. Subcircuits Ni* are connected exactly as Ni, forming a circuit N* whose outputs are functionally equivalent (modulo negation) to corresponding outputs of N.
The TEQLS procedure is linear in the number of subcircuits Ni and exponential in the sizes of Ni and Ni*. Hence, TEQLS has linear complexity if the size of subcircuits Ni and Ni* is bounded (which in practice, still leaves a huge number of candidate circuits). This efficiency stems from the fact that when replacing a subcircuit Ni with a subcircuit Ni*, their toggle equivalence is maintained only locally in terms of input variables of Ni and Ni*, related by so-called correlation functions, which are described in the TEQLS references and which can be efficiently computed.
Recently, Sets of Pairs of Functions to be Distinguished (SPFDs) were introduced as a new way to do logic optimization. Although SPFDs were introduced in the context of FPGA synthesis, S. Yamashita, H. Sawada, and A. Nagoya, “A new method to express functional permissibilities for LUT based FPGAs and its applications;” in Proc. of IEEE International Conference on Computer-Aided Design, pp. 254-61, November 1996, they have been applied in the context of multi-level combinational network synthesis as well, R. Brayton, “Understanding SPFDs: A new method for specifying flexibility,” in Proc. of the International Workshop on Logic Synthesis, (Tahoe City, Calif.), May 1997 and S. Sinha and R. Brayton, “Implementation and use of SPFDs in optimizing boolean networks,” in Proc. of IEEE International Conference an Computer-Aided Design, pp. 103-10, November 1998. They have been generalized to multi-valued variables R. Brayton, Supra. and S. Khatri, S. Sinha, R. Brayton, and A. Sangiovanni-Vincentelli, “SPFD-based wire removal in standard-cell and network-of-PLA circuits,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, pp. 1020-1030, July 2004 as well as to sequential synthesis S. Sinha, A. Kuehlmann, and R. Brayton, “Sequential SPFDs,” in Proc. of IEEE International Conference on Computer-Aided Design, pp. 84-90, November 2001. More recently, SPFDs have been applied to the problem of topologically constrained logic synthesis S. Sinha, A. Mishchenko, and R. Brayton, “Topologically constrained logic synthesis;” in Proc. of IEEE International Conference on Computer-Aided Design, pp. 679-686, November 2002.
A toggle is simply an SPFD edge. Therefore, both SPFDs and TEQLS use an “optimization as communication” paradigm. By replacing subcircuits Ni with their toggle equivalent counterparts Ni*, TEQLS essentially “redistributes” complexity between these subcircuits. In other words, subcircuits “talk” to each other through particular choices of encodings. A similar paradigm is used in the method of SPFDs.
One difference between TEQLS and SFPDs is that TEQLS is scalable because there is freedom in choosing the subcircuits to be replaced with their toggle equivalent counterparts and therefore control over sizes. More specifically, TEQLS provides an efficient procedure for finding optimized circuit N*, the essence of which is replacing subcircuits Ni of N with toggle equivalent counterparts Ni*. The set of candidate circuits is well-defined and huge. To realize how vast the set of candidate circuits is, it suffices to say that the number of k-output functions toggle equivalent to a k-output function ƒi (implemented by subcircuit Ni) is (2k)!. (Here we assume that all 2k output assignments of ƒ are satisfiable.) This number, for k=1, 2, 3, 4 and 5 is 2, 24, 4·104, 2.1·1013 and 2.6·1035 respectively. As a consequence, TEQLS enjoys enormous optimization flexibility even if the subcircuits Ni are small. Unfortunately, the TEQLS references do not provide a procedure that, given a subcircuit Ni, would build a toggle equivalent subcircuit Ni*.
In contrast, in SFPDs, the propagation of toggles from outputs to inputs is controlled by the topology of the optimized circuit. One shortcoming of SFPDs is that SFPDs start with the desired functional requirement (SFPD edges) at the outputs and propagates them backwards towards the inputs, while constructing the multi-level logic in the process. As a result, SPFDs are limited in the choice of candidate circuits by the topology of the original circuit.
Thus, there has been a need for a procedure to build a toggle equivalent subcircuit. The present invention meets this need.